Thực đơn
Bổ đề Johnson–Lindenstrauss Phát biểuVới mọi 0 < ε < 1, tập hợp X gồm m điểm trong RN, và một số nguyên n > n 0 = O(ln(m) / ε 2), tồn tại một hàm Lipschitz ƒ : RN → Rn sao cho
( 1 − ε ) ‖ u − v ‖ 2 ≤ ‖ f ( u ) − f ( v ) ‖ 2 ≤ ( 1 + ε ) ‖ u − v ‖ 2 {\displaystyle (1-\varepsilon )\|u-v\|^{2}\leq \|f(u)-f(v)\|^{2}\leq (1+\varepsilon )\|u-v\|^{2}}với mọi u, v ∈ X.
Một cách chứng minh bổ đề là chọn ƒ là phép chiếu xuống một không gian ngẫu nhiên n chiều trong RN, và sử dụng hiện tượng tập trung độ đo.
Số chiều của bổ đề là chặt cho tới thừa số log(1/ε), nghĩa là tồn tại m điểm sao cho để giữ nguyên khoảng cách giữa các điểm tới thừa số 1+ε, cần sử dụng
Ω ( log ( m ) ε 2 log ( 1 / ε ) ) {\displaystyle \Omega \left({\frac {\log(m)}{\varepsilon ^{2}\log(1/\varepsilon )}}\right)}chiều.[1]
Thực đơn
Bổ đề Johnson–Lindenstrauss Phát biểuLiên quan
Tài liệu tham khảo
WikiPedia: Bổ đề Johnson–Lindenstrauss http://people.ee.duke.edu/~lcarin/p93.pdf http://dsp.rice.edu/files/cs/JL_RIP.pdf http://www-cse.ucsd.edu/~dasgupta/papers/jl-tr.ps http://www.math.tau.ac.il/~nogaa/PDFS/extremal1.pd... //dx.doi.org/10.1007%2Fs00365-007-9003-x